<?php
/**
 * @title 63. 不同路径 II - 穷列
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[][] $obstacleGrid
     * @return Integer
     */
    function uniquePathsWithObstacles($obstacleGrid) {
        /**
         * * 0 → → m
         * ↓
         * ↓
         * n
         * @since 2020-07-23 极端情况排除
         */
        $n = count($obstacleGrid);
        if($n == 0){
            return 0;
        } else {}
        $m = count($obstacleGrid[0]);
        if($m == 0){
            return 0;
        } else {}

        /**
         * @since 2020-07-23 每个点路径集
         */
        $dps = [];
        $dps[0][0] = 1-$obstacleGrid[0][0];

        /**
         * @since 2020-07-23 减少isset判断, 提前计算好第一行和第一列
         * @since 2020-07-23 计算第一行
         */
        for($i=1; $i<$m; $i++){
            if($obstacleGrid[0][$i]==0 AND $dps[0][$i-1]){
                $dps[0][$i] = 1;
            } else {
                $dps[0][$i] = 0;
            }
        }

        /**
         * @since 2020-07-23 计算第一列
         */
        for ($i=1; $i<$n; $i++){
            if($obstacleGrid[$i][0]==0 AND $dps[$i-1][0]){
                $dps[$i][0] = 1;
            } else {
                $dps[$i][0] = 0;
            }
        }

        /**
         * @since 2020-07-06 穷列
         */
        for ($i=1; $i<$n; $i++){
            for ($j=1; $j<$m; $j++){
                /**
                 * @since 2020-07-23 dp(m,n)=nums[n−1][m−1]∗(dp(m,n−1)+dp(m−1,n))
                 */
                if($obstacleGrid[$i][$j]==0){
                    $dps[$i][$j] = $dps[$i][$j-1] + $dps[$i-1][$j];
                } else {
                    $dps[$i][$j] = 0;
                }
            }
        }

        /**
         * @return
         */
        return $dps[$n-1][$m-1];
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.06_2.php
 */
$datas = [
    [
        [0,0,0],
        [0,1,0],
        [0,0,0]
    ],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->uniquePathsWithObstacles($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
